
import os
import sys

# 把包的父目录添加到系统搜索路径
BASE_DIR = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
sys.path.append(BASE_DIR)

from base_data_structures.graph import Graph, Vertex
from base_data_structures.queue import Queue
 
def buildGraph(wordFile):
    d = {}
    g = Graph()
    wfile = open(wordFile, 'r')

    for line in wfile:
        word = line[:-1]
        for i in range(len(word)):
            bucket = word[:i] + "_" + word[i+1:]
            if bucket in d:
                d[bucket].append(word)
            else:
                d[bucket] = [word]
    # 添加顶点和边
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1, word2)
    return g

def bfs(g, start):
    start.setDistance(0)
    start.setPred(None)

    vertQueue = Queue()
    vertQueue.enqueue(start)
    
    while vertQueue.size() > 0:
        currentVert = vertQueue.dequeue()
        # 获取当前节点所有邻接节点， 然后入队， 等候处理
        for nbr in currentVert.getConnections():
            # white表示未处理过的顶点
            if nbr.getColor()=='white':
                nbr.setColor('gray')
                nbr.setDistance(currentVert.getDistance()+1)
                nbr.setPred(currentVert)
                vertQueue.enqueue(nbr)
        currentVert.setColor('black')

def traverse(y):
    x = y
    while x.getPred():
        print(x.getId())
        x=x.getPred()
    print(x.getId())

g = buildGraph('graph_app/fourletterwords.txt')
bfs(g, g.getVertex('FOOL'))
traverse(g.getVertex('SAGE'))